"""
2106. 摘水果
困难
相关标签
premium lock icon
相关企业
提示
在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。



示例 1：


输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果
示例 2：


输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：
可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果
示例 3：


输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：
最多可以移动 k = 2 步，无法到达任一有水果的地方


提示：

1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
对于任意 i > 0 ，positioni-1 < positioni 均成立（下标从 0 开始计数）
1 <= amounti <= 104
0 <= k <= 2 * 105
"""
from bisect import bisect_left, bisect_right
from typing import List


class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        ansL = self.method_name(fruits, k, startPos)
        # 获取最大位置用于镜像
        max_pos = fruits[-1][0] + 1

        # 创建镜像后的fruits数组，但保持位置顺序
        mirrored_fruits = [[max_pos - pos , amount] for pos, amount in fruits]
        # 需要重新排序以保持位置升序
        mirrored_fruits.sort()
        print(mirrored_fruits)

        # 镜像后的起始位置
        mirrored_startPos = max_pos - startPos

        # 镜像逻辑
        ansR = self.method_name(mirrored_fruits, k,mirrored_startPos)

        return max(ansL, ansR)

            # rCount = preDP[i] - preDP[startPos - 1]
            # err = k - 2 * (i - startPos)
            # if err>0:

    def method_name(self, fruits, k,  startPos):

        len1 = fruits[-1][0] + 1 #todo 考虑去掉前面无意义的？
        dp = [0] * len1  # 前缀和
        preDP = [0] * len1  # 前缀和
        for i in range(len(fruits)):
            dp[fruits[i][0]] = fruits[i][1]
        # print(dp)
        for i in range(1, len1):
            preDP[i] = dp[i] + preDP[i - 1]
        print(preDP)
        # 优先向右？？
        ans = dp[startPos]
        # 找到最右能达到的点
        startR = -1
        countR = 0
        startL = -1
        countL = 0
        diff = -1
        for i in range(len1 - 1, startPos, -1):
            if k >= i - startPos:
                startR = i
                countR = preDP[i] - preDP[startPos]
                # 还能向左走
                diff = k - 2 * (i - startPos)
                if diff > 0:
                    for i in range(startPos - 1, 0, -1):
                        if startPos - i > diff:
                            continue
                        else:
                            startL = i
                            countL += dp[i]
                ans = max(ans, countL + countR + dp[startPos])
                break
        for i in range(len1 - 2, startPos, -1):
            diff-= 1
            if diff<0:
                break
            # print(i)
            countR -= dp[i + 1]
            startR -= 1
            countL += dp[i]
            ans = max(ans, countL + countR + dp[startPos])
        return ans
    #todo
    def maxTotalFruits_res1(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]
        right = bisect_left(fruits, [startPos + 1])  # 位置 <= startPos 的最大下标 + 1
        ans = s = sum(f[1] for f in fruits[left: right])  # 从 fruits[left][0] 到 startPos 的水果数
        # 枚举最右走到 fruits[right][0]
        while right < len(fruits) and fruits[right][0] <= startPos + k:
            s += fruits[right][1]
            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \
                  fruits[right][0] - fruits[left][0] * 2 + startPos > k:
                s -= fruits[left][1]  # fruits[left][0] 太远了
                left += 1
            ans = max(ans, s)  # 更新答案最大值
            right += 1  # 继续枚举下一个最右位置
        return ans
    def maxTotalFruits_res2(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]
        ans = s = 0
        for pos, amount in fruits[left:]:
            if pos > startPos + k:
                break
            s += amount
            while pos * 2 - fruits[left][0] - startPos > k and \
                  pos - fruits[left][0] * 2 + startPos > k:
                s -= fruits[left][1]  # fruits[left][0] 太远了
                left += 1
            ans = max(ans, s)  # 更新答案最大值
        return ans


if __name__ == '__main__':
    # print(Solution().maxTotalFruits([[2,8],[6,3],[8,6]],5,4))
    # print(Solution().maxTotalFruits([[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]],5,4))
    # print(Solution().maxTotalFruits([[0,3],[6,4],[8,5]],5,4))
    # print(Solution().maxTotalFruits_res1([[2,8],[6,3],[8,6]],5,4))
    # print(Solution().maxTotalFruits_res1([[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]],5,4))
    # print(Solution().maxTotalFruits_res1([[0,3],[6,4],[8,5]],5,4))

    dp1 = [1,3,4]
    print(bisect_left(dp1,2))
    print(bisect_left(dp1,2+1))
    arr = [1, 2, 2, 2, 3, 4]
    x = 2

    # bisect_left 返回第一个 >= x 的位置
    print(bisect_left(arr, x))    # 输出: 1 (第一个2的位置)

    # bisect_right 返回第一个 > x 的位置
    print(bisect_right(arr, x))   # 输出: 4 (第一个大于2的元素3的位置)

    # 对于不存在的元素
    x = 2.5
    print(bisect_left(arr, x))    # 输出: 4 (第一个>=2.5的位置)
    print(bisect_right(arr, x))   # 输出: 4 (第一个>2.5的位置)